package com.leaves.leetcode.array.t18_4Sum;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


/**
 * 核心要点：
 * 排序+双指针+剪枝
 * 1、通过确定first和third，判断双指针扫描左右侧最大最小值情况来过滤不必要的遍历
**/
 class Solution {

    /**
     * 排序+双指针+剪枝
     * 1、通过确定first和third，判断双指针扫描左右侧最大最小值情况来过滤不必要的遍历
     * 2、最后落到third和fourth的双指针遍历上，要注意2个问题1)为了减少累加参数个数，用subTarget作为双指针对应两个数的目标值 2）注意固定third后fourth遍历到third+1的情况，因为for循环的对fourth的迭代会让fourth=third或third+1，会导致最后的==判断无法生效
     * 时间复杂度：O(n^3)
     * 空间复杂度：O(nlogn) 排序空间
     * @param nums
     * @param target
     * @return
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        int n = nums.length;
        // 为了避免Map去重元组，先将数组排序，在遍历过程中去重
        Arrays.sort(nums);

        for (int first = 0; first < n - 3; first++) {
            // 去重
            if (first > 0 && nums[first] == nums[first - 1]) continue;

            // 优化1： 固定了first，若nums[first] + nums[first+1] + nums[first+2] + nums[first+3] > target，那之后所有的四元组都会大于target，此时可退出第一层循环
            if ((long) nums[first] + nums[first+1] + nums[first+2] + nums[first+3] > target) break;

            // 优化2： 固定了first，若nums[first] + nums[n-3] + nums[n-2] + nums[n-1] < target，说明该first下的所有四元组都不会大于target，此时可遍历下一个first
            if ((long)nums[first] + nums[n-3] + nums[n-2] + nums[n-1] < target) continue;

            for (int second = first + 1; second < n - 2; second++) {
                // 去重
                if (second > first + 1 && nums[second] == nums[second - 1]) continue;

                // 优化3： 固定了first和second，若nums[first] + nums[second] + nums[second+1] + nums[second+2] > target，那之后所有second，third和fourth组合的四元组都会大于target，可退出第二层循环了
                if ((long)nums[first] + nums[second] + nums[second+1] + nums[second+2] > target) break;

                // 优化4： 固定了fitst和second，若nums[first] + nums[second] + nums[n-2] + nums[n-1] < target，那之后的hird和fourth组合的四元组都会小于target，此时可以遍历下一个second
                if ((long)nums[first] + nums[second] + nums[n-2] + nums[n-1] < target) continue;

                int subTarget = target - nums[first] - nums[second];
                int fourth = n - 1;
                for (int third = second + 1; third < fourth; third++) {
                    // 去重
                    if (third > second + 1 && nums[third] == nums[third - 1]) continue;
                    if (nums[third] + nums[fourth] > subTarget) {
                        while (third < fourth && nums[third] + nums[fourth] > subTarget) fourth--;
                    }
                    if (third < fourth && nums[third] + nums[fourth] == subTarget) res.add(Arrays.asList(nums[first], nums[second], nums[third], nums[fourth]));
                }
            }
        }
        return res;
    }
}